606D - Lazy Student - CodeForces Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <iomanip>
#include <iterator>
#include <cmath>
#include <map>
#include <string.h>
#include <ctime>
#include <queue>
#include<unordered_map>
#include<stack> 
#include<unordered_set>
#define Tamora ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ld long double
using namespace std;

vector<int>dirx{ 1,-1, 0,0,1,1,-1,-1 };
vector<int>diry{ 0,0,-1,1,1,-1,1,-1 };

bool valid(int n, int m, int x, int y) {
	return x >= 0 && y >= 0 && x < n&& y < m;
}

ll gcd(ll a, ll b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return (a * b) / gcd(a, b);
}

const ll mod = 1e9, inf = 1e18, N = 3e5 + 5, M = 1e3 + 5;

bool cmp(pair<pair<int, int>, int>a, pair<pair<int, int>, int>b) {
	return a.first.first < b.first.first || (a.first.first == b.first.first && b.first.second < a.first.second);
}

void solve() {
	int n, m;
	cin >> n >> m;
	vector<pair<pair<int, int>,int>>edge(m);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		edge[i] = { { a,b},i };
	}
	sort(all(edge),cmp);
	vector<int>tree{ 1 };
	vector<pair<int,int>>ans(m);
	int nxt = 2;
	vector<pair<int,int>>av;
	int rem = m;
	for (auto i : edge) {
		int b = i.first.second, ind = i.second;
		if (b) {
			for (int i = 2; i <= tree.size() && av.size() < rem; i++)
				av.push_back({ i,nxt });
			tree.push_back(nxt), ans[ind] = { 1,nxt++ };
		}
		else
			if (!av.empty())
				ans[ind] = av.back(), av.pop_back();
			else
				return void(cout << -1);
		rem--;
	}
	for (auto i : ans)
		cout << i.first << ' ' << i.second << endl;
}


//void files() {
//
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//}


int main() {
	Tamora;
	/*int t; cin >> t;
	while (t--)*/
	solve();

}